package com.xyj.review;

import com.xyj.week01.Node;
import com.xyj.week01.T4;

/**链表归并排序
 * @author GuXiaoYao
 * @version 1.0.0
 * @since 2021/9/9
 */
public class T3 {

    public static void main(String[] args) {
        //初始化环形链表
        Node node = new Node(5);
        Node node1 = new Node(6);
        Node node2 = new Node(7);
        Node node3 = new Node(8);
        Node node4 = new Node(4);
        node.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        System.out.println("排序前的链表为");
        Node help =node;
        while (help!=null){
            System.out.println(help);
            help=help.next;
        }
        Node process = process(node);
        System.out.println("排序后的链表为");
        while (process!=null){
            System.out.println(process);
            process=process.next;
        }
    }
    public static Node process(Node head){
        if (head==null||head.next==null){
            return head;
        }
        //将链表分为两部分
        Node middleNode = T4.getTheMidNode(head);
        Node rightHeadNode=middleNode.next;
        //左边链表断开连接
        middleNode.next=null;
        //链表分为两部分  然后排序链表
        return mergeSort(process(head),process(rightHeadNode));
    }



    private static Node mergeSort(Node leftHeadNode, Node rightHeadNode) {
        Node help=new Node(-1);
        Node sortNode=help;
        // 链表排序
        while (leftHeadNode!=null&&rightHeadNode!=null){

            if(leftHeadNode.value>rightHeadNode.value){
                //左边大的时候将右边节点赋值给链表
                sortNode.next=rightHeadNode;
                rightHeadNode=rightHeadNode.next;
            }else {
                sortNode.next=leftHeadNode;
                leftHeadNode=leftHeadNode.next;
            }
            sortNode=sortNode.next;
        }
        if (leftHeadNode!=null){
            // 左边还有节点
            sortNode.next=leftHeadNode;
        }else {
            // 右边还有节点
            sortNode.next=rightHeadNode;
        }
        return help.next;
    }


    public static Node getTheMiddleNode(Node head){
        Node slow=head;
        Node fast=head;
        while (fast.next!=null&&fast.next.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        return slow;
    }
}
